from pythonds import  BinaryTree;
# 先序遍历 中左右
def preorderTraversl(root):
    # 保存结果
    result=[]

    def traversal(root):
        # 确定终止条件
        if root==None:
            return
        # 前序遍历顺序 中左右
        result.append(root.key) #中
        traversal(root.getLeftChild()) # 左
        traversal(root.getRightChild()) # 右
    # 进入traversal()方法
    traversal(root)
    return result
# 中序遍历 左中右
def inorderTraversal(root):
    # 保存结果
    result=[]

    def traversal(root):
        # 终止条件
        if root==None:
            return
        # 中序遍历顺序 左中右
        traversal(root.getLeftChild()) #左
        result.append(root.key) #中
        traversal(root.getRightChild()) #右
    traversal(root)
    return result
# 后序遍历 左右中
def afterorderTraversal(root):
    # 保存结果
    result=[]
    def traversal(root):
        # 终止条件
        if root==None:
            return
        # 后序遍历顺序 左右中
        traversal(root.getLeftChild())
        traversal(root.getRightChild())
        result.append(root.key)
    traversal(root)
    return result

# root=BinaryTree('A')
# root.insertLeft('B')
# root_left=root.getLeftChild()
# root_left.insertLeft("D")
# root_left.insertRight("E")
# root_left_right=root_left.getRightChild()
# root_left_right.insertRight("J")
# root.insertRight("C")
# root_right=root.getRightChild()
# root_right.insertLeft("F")
# root_right_left=root_right.getLeftChild()
# root_right_left.insertRight("I")
# root_right.insertRight("G")
# print("先序遍历:",preorderTraversl(root))
# print("中序遍历:",inorderTraversal(root))
# print("后序遍历:",afterorderTraversal(root))

root2=BinaryTree(10)
root2.insertLeft(6)
root2_left=root2.getLeftChild()
root2_left.insertLeft(3)
root2_left.insertRight(9)
root2.insertRight(16)
print("先序遍历:",preorderTraversl(root2))
print("中序遍历:",inorderTraversal(root2))
print("后序遍历:",afterorderTraversal(root2))
